package com.tgy.algorithm._经典题目01;

/**
 *
 *  [2,1,3,4,2,5]
 *  [1,]
 */
public class _024_最长递增子序列 {

    public static int maxIncrementalSubArr(int[] nums) {

        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        int[] lens = new int[len];
        lens[0] = 1;
        int staff = 0;
        for (int i = 1; i < len; i++) {
            int value = nums[i];
            int left = 0;
            int right = staff;
            int local = staff+1;
            while (left <= right) {
                int mid = left + ((right - left) >> 1);
                if (lens[mid] >= value) {
                    local = mid;
                    right = mid - 1;
                }else {
                    left = mid + 1;
                }
            }
            lens[local] = value;
            if (local > staff) {
                staff++;
            }
        }

        return staff+1;
    }

    public static void main(String[] args) {


    }
}
